<!DOCTYPE html>
<html>
  <head>
    <title>Numεrωmikωn</title>
    <link rel="stylesheet" href="../stock.css">
    <link rel="icon" type="image/x-icon" href="../favicon.ico">
    <meta content="text/html;charset=utf-8" http-equiv="Content-Type"/>
    <meta name="viewport" content="width=device-width, initial-scale=1" />
  </head>

  <body>
    <div class ="nav">
      <a href="../index">Indεχ</a>
      <a href="../clanky">Článκy</a>
      <a class="active" href="../googologie">Gωωgωlωgiε</a>
      <a href="../o_mne">Ω mně</a>
    </div>

    <div class="content-googology">
      <h1>Rekurzivní expanze ~ <i>f<sub>ω + 2</sub>(n)</i></h1>

      <p>Prozkoumáme, jak se naše Wainerovská rychle rostoucí hierarchie chová, obsahuje-li v indexu <i>ω</i>. Zatím nepotřebujeme vědět, jak zacházet s
      nekonečnými ordinály; stačí nám vědět, jak přejít z <i>ω</i> na konečné číslo. Pro připomenutí:</p>

      <div class="math"> 
        <p>f<sub>ω</sub>(n) = f<sub>n</sub>(n)</p>
      </div>

      <p>------</p>

      <p>Zkusíme přirovnat rychle rostoucí funkce k šipkovému zápisu. Již víme, že <i>f<sub>1</sub>(n)</i> zdvojnásobuje vstup. Taky si pamatujeme výsledek 
      <i>f<sub>2</sub>(3)</i>:</p>

      <div class="math"> 
        <p>f<sub>2</sub>(3) = 24</p>
      </div>

      <p>Protože zdvojnásobíme trojku, pak výsledek z ní a nakonec i to zdvojnásobíme; <i>3 * 2 * 2 * 2</i>. Zkusme si víc příkladů:</p>

      <div class="math"> 
        <p>f<sub>2</sub>(4) = 4 * 2 * 2 * 2 * 2 = 64</p>
      </div>

      <p>Všimněme si jednoduchého vzorce:</p>

      <div class="math"> 
        <p>f<sub>2</sub>(n) = 2<sup>n</sup> * n</p>
      </div>

      <p>------</p>

      <p>Nyní zvýšíme index o <i>1</i> a budeme opakovat <i>f<sub>2</sub>(n)</i>:</p>

      <div class="math"> 
        <p>f<sub>3</sub>(n) = f<span class="supsub"><sup>n</sup><sub>2</sub></span>(n)</p>
      </div>

      <p>------</p>

      <p>Zkusme si vypočítat jeden příklad:</p>

      <div class="math"> 
        <p>f<sub>3</sub>(3) = f<sub>2</sub>(f<sub>2</sub>(f<sub>2</sub>(3)))</p>
      </div>

      <p>Víme, že výsledek z <i>f<sub>2</sub>(3)</i> je <i>24</i>. Co to znamená? Že 24 bude další vstup:</p>

      <div class="math"> 
        <p>f<sub>2</sub>(f<sub>2</sub>(24))</p>
      </div>

      <p>To jsme taky schopni zjednodušit:</p>

      <div class="math">
        <p>f<sub>2</sub>(24) = 2<sup>24</sup> * 24</p>
        <p>2<sup>24</sup> * 24 = 402653184</p>
      </div>

      <p>Nyní bychom toto použili jako poslední vstup:</p>

      <div class="math"> 
        <p>f<sub>2</sub>(402653184) = 2<sup>402653184</sup> * 402653184</p>
      </div>

      <p>------</p>

      <p>To je velké číslo a spodní index je teprve ordinál <i>2</i>! Obecně vztah mezi rychle rostoucí hierarchií a hyperexponenty je takový:</p>

      <div class="math"> 
        <p>f<sub>x</sub>(n) ≥ 2 ↑<sup>x - 1</sup> n</p>
      </div>

      <p>------</p>

      <p>U hyperexponentů ovlivňuje rychlost růstu hlavně počet šipek, pak číslo vpravo; číslo vlevo téměř nemá vliv. Proto můžeme říci:</p>

      <div class="math"> 
        <p>f<sub>x</sub>(3) ~ 3 ↑<sup>x - 1</sup> 3</p>
      </div>

      <p>------</p>

      <p>Vraťme se ke Grahamovu číslu. Pravil jsem, že <i>f<sub>ω + 1</sub>(64)</i> je přibližně to samé jako <i>g<sub>64</sub></i>. Podívejme
      se na to zblízka:</p>

      <div class="math"> 
        <p>f<sub>ω + 1</sub>(64) = f<span class="supsub"><sup>64</sup><sub>ω</sub></span>(64)</p>
      </div>

      <p>První krok bude zjistit hodnotu <i>f<sub>ω</sub>(64)</i>:</p>

      <div class="math">
        <p>f<sub>ω</sub>(64) = f<sub>64</sub>(64)</p>
        <p>f<sub>64</sub>(64) ≥ 2 ↑<sup>63</sup> * 64</p>
      </div>

      <p>------</p>

      <p>To bude zajisté obrovské číslo! Jelikož počet šipek je mnohem důležitější pro rychlost růstu než číslo vlevo, je jasné, že 
      <i>2 ↑<sup>63</sup> * 64</i> bude výrazně větší než <i>3 ↑↑↑↑ 3</i>, ale zkus si to potvrdit.</p>

      <p>Nyní bychom využili výsledek tohoto čísla jako index další rychle rostoucí funkce. Postup je velmi podobný Grahamově
      funkci. Ale co kdybychom zvetšili index na <i>ω + 2</i>? Zkusme:</p>

      <div class="math"> 
        <p>f<sub>ω + 2</sub>(64) = f<span class="supsub"><sup>64</sup><sub>ω + 1</sub></span>(64)</p>
      </div>

      <p>------</p>

      <p>Už teď by mělo být jasné, co se bude dít. Nejvnořenější funkce bude <i>f<sub>ω + 1</sub>(64)</i>, tedy přibližně Grahamovo číslo.
      To znamená, že následující funkce je asi taková:</p>

      <div class="math"> 
        <p>f<sub>ω + 1</sub>(g<sub>64</sub>)</p>
      </div>

      <p>Víme, že <i>f<sub>ω + 1</sub>(x)</i> roste obdobně rychle jako g<sub>x</sub>. Tudíž máme:</p>

      <div class="math"> 
        <p>f<sub>ω + 1</sub>(f<sub>ω + 1</sub>(64)) ~ g<sub>g<sub>64</sub></sub></p>
      </div>

      <p>To, co jsme opakovali 64krát, abychom dostali Grahamovo číslo, bychom nyní opakovali <i>Grahamovo-číslo</i>krát! A to jsme teprve
      u druhé funkce. Kdybychom to tedy dovedli až do konce:</p>

      <div class="math"> 
        <p>f<sub>ω + 2</sub>(64) ~ g<sub>g<sub>(...)<sub>g<sub>64</sub></sub></sub></sub></p>
      </div>

      <p>------</p>

      <p>Česky by to znělo: Grahamovu funkci opakujme 64krát, výsledným číslem opakujme Grahamovu funkci, teď tím znovu 
      opakujme Grahamovu funkci, znovu, znovu, znovu (...)</p>

      <p>Zkus si představit, jak by to asi vypadalo, kdybychom znovu zvětšili index o 1! Rozepisovat bych to opravdu nechtěl.</p>

      <p>Začali jsme u tetrace a porazili jsme Grahamovo číslo. Viděli jsme na vlastní oči, jak mocná rychle rostoucí hierarchie je. Hned za rohem
      číhá ale něco mnohem většího a děsivějšího: Goodsteinova věta.</p>
    </div>

    <footer>
      <p class="footer"><a class="silent" href="https://creativecommons.org/licenses/by/4.0/" target="_blank">Kristian Tichota (CC-BY-4.0)</a></p>
    </footer>
  </body>
</html>
